package com.shawn.datastructure.linkedlist;

public class LinkedListAlgo {

	// 单链表反转 1->2->3  3->2->1
	public static Node reverse(Node list) {
		Node cur = list;
		Node pre = null;
		while (cur != null) {
			Node next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}

	// 判断回文
	public boolean isPalindrome(Node node) {
		// 如果Node为null，或者node只有一个结点，那么node就是回文链表
		if (node == null || node.next == null) {
			return true;
		}

		Node p = node;
		Node q = node;
		Node pre = null;
		// 开始查找mid node
		while (q != null && q.next != null) {
			q = q.next.next;
			Node next = p.next;
			p.next = pre;
			pre = p;
			p = next;
		}

		if (q != null) {
			p = p.next;
		}

		while (p != null) {
			if (p.data != pre.data) {
				return false;
			}
			p = p.next;
			pre = pre.next;
		}

		return true;
	}

	// 检测环
	public static boolean checkCircle(Node list) {
		if (list == null) {
			return false;
		}
		Node slow = list;
		Node fast = list.next;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
			if (fast == slow) {
				return true;
			}
		}
		return false;
	}

	// 合并两个有序链表
	public static Node mergeSortedLists_1(Node la, Node lb) {
		if (la == null) {
			return lb;
		}
		if (lb == null) {
			return la;
		}

		Node p = la;
		Node q = lb;
		Node head;

		if (p.data < q.data) {
			head = p;
			p = p.next;
		} else {
			head = q;
			q = q.next;
		}

		Node r = head;
		while (p != null && q != null) {
			if (p.data < q.data) {
				r.next = p;
				p = p.next;
			} else {
				r.next = q;
				q = q.next;
			}
			r = r.next;
		}

		if (p != null) {
			r.next = p;
		} else {
			r.next = q;
		}
		return head;
	}

	public static Node mergeSortedLists_2(Node la, Node lb) {
		Node p = new Node(0, null);
		Node r = p;

		while (la != null && lb != null) {
			if (la.data < lb.data) {
				r.next = la;
				la = la.next;
			} else {
				r.next = lb;
				lb = lb.next;
			}
			r = r.next;
		}

		if (la != null) {
			r.next = la;
		} else {
			r.next = lb;
		}
		return p.next;
	}

	// 合并 k 个排序链表
	public static Node mergeKLists(Node[] nodes) {
		return mergeList(nodes, 0, nodes.length - 1);
	}

	private static Node mergeList(Node[] nodes, int begin, int end) {
		if (begin > end) {
			return null;
		}
		if (begin == end) {
			return nodes[begin];
		}
		int mid = (begin + end) >> 1;
		Node listNode1 = mergeList(nodes, begin, mid);
		Node listNode2 = mergeList(nodes, mid + 1, end);
		Node merges = mergeSortedLists_2(listNode1, listNode2);
		return merges;
	}

	// 求链表的中间结点
	public static Node findMiddleNode(Node list) {
		if (list == null) {
			return null;
		}

		Node fast = list;
		Node slow = list;

		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}

		return slow;
	}

	// 删除链表倒数第n个结点
	public static Node deleteLastKth(Node list, int k) {
		Node fast = list;
		int i = 1;
		while (fast != null && i < k) {
			fast = fast.next;
			++i;
		}
		if (fast == null) {
			return list;
		}
		Node slow = list;
		Node prev = null;
		while (fast.next != null) {
			fast = fast.next;
			prev = slow;
			slow = slow.next;
		}

		if (prev == null) {
			list = list.next;
		} else {
			prev.next = prev.next.next;
		}
		return list;
	}

	public static class Node {

		private int data;
		private Node next;

		public Node(int data, Node next) {
			this.data = data;
			this.next = next;
		}

		public int getData() {
			return data;
		}
	}

}
